You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.
You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
Example 1:
Input: amount = 5, coins = [1,2,5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10] Output: 1
Constraints:
1 <= coins.length <= 3001 <= coins[i] <= 5000- All the values of
coinsare unique. 0 <= amount <= 5000
Average Rating: 4.12 (83 votes)
Solution
Approach 1: Dynamic Programming
Template
This is a classical dynamic programming problem.
Here is a template one could use:
-
Define the base cases for which the answer is obvious.
-
Develop the strategy to compute more complex case from more simple one.
-
Link the answer to base cases with this strategy.
Example
Let's pic up an example: amount = 11, available coins - 2 cent, 5 cent and 10 cent. Note, that coins are unlimited.
Base Cases: No Coins or Amount = 0
If the total amount of money is zero, there is only one combination: to take zero coins.
Another base case is no coins: zero combinations for amount > 0 and one combination
for amount == 0.
2 Cent Coins
Let's do one step further and consider the situation with one kind of available coins: 2 cent.
It's quite evident that there could be 1 or 0 combinations here, 1 combination for even amount and 0 combinations for the odd one.
The same answer could be received in a recursive way, by computing the number of combinations for all amounts of money, from 0 to 11.
First, that's quite obvious that all amounts less than 2
are not impacted by the presence of 2 cent coins. Hence
for amount = 0 and for amount = 1 one could reuse the results
from the figure 2.
Starting from amount = 2, one could use 2 cent coins in the combinations.
Since the amounts are considered gradually from 2 to 11, at each given
moment one could be sure to add not more than one coin to the previously
known combinations.
So let's pick up 2 cent coin, and use it
to make up amount = 2. The number of combinations with
this 2 cent coin is a number combinations for amount = 0,
i.e. 1.
Now let's pick up 2 cent coin, and use it
to make up amount = 3. The number of combinations with
this 2 cent coin is a number combinations for amount = 1,
i.e. 0.
That leads to DP formula for number of combinations to make up
the amount = x: dp[x] = dp[x] + dp[x - coin], where coin = 2 cents
is a value of coins we're currently adding.
2 Cent Coins + 5 Cent Coins + 10 Cent Coins
Now let's add 5 cent coins. The formula is the same,
but do not forget to add dp[x], number of combinations with
2 cent coins.
The story is the same for 10 cent coins.
Now the strategy is here:
-
Add coins one-by-one, starting from base case "no coins".
-
For each added coin, compute recursively the number of combinations for each amount of money from 0 to
amount.
Algorithm
-
Initiate number of combinations array with the base case "no coins":
dp[0] = 1, and all the rest = 0. -
Loop over all coins:
-
For each coin, loop over all amounts from 0 to
amount:- For each amount x, compute the number of combinations:
dp[x] += dp[x - coin].
- For each amount x, compute the number of combinations:
-
-
Return
dp[amount].
Implementation
Complexity Analysis
-
Time complexity: O(N×amount), where N is a length of coins array.
-
Space complexity: O(amount) to keep dp array.
Last Edit: June 10, 2020 1:35 PM
The fun part about this solution is that if you switch the order of the for loops in the code, your answer almost doubles! Learnt it the hard way.
If you're wondering why, here's a hint:
To make an amount of 3 with two coin denominations 1 and 2, you can go:
1 + 2 = 3
2 + 1 = 3
Both mean the same thing, in this question.
April 2, 2020 12:46 PM
great article...it would be great if you guys can first explain top down approach..then bottom up
Last Edit: June 8, 2020 12:58 AM
Although the implementation looks super easy and so does the explanation neither of them is. Moreover, it is dangerously confusing. The dp relationship dp[x] = dp[x] + dp[x - coin] depends on itself, which is not permitted for dynamic programming. Optimal substructure is not shown. So this is indeed a solution, but it is not a dynamic programming one (strictly speaking at least). The problem can be solved with DP, however, for which you need a two dimensional DP array.
June 8, 2020 6:26 AM
I would say the dp formula dp[x] += dp[x - coin] can be explained as
The combination of i number of coins to make change for j amount = The combination when we not using ith coin to make change for j amount + The combination when we use ith coin to make change for j amount.
It likes knapsack problem, calculate the result when we pick the current coin and not pick it and get the total
Last Edit: June 23, 2020 10:45 PM
This explanation explains how to do the problem, but doesn't fully explain how we get from the two dimensional representation to the 1D version. Or why that works. The entire explanation is two-D then suddenly we are in some optimized form.
Sadly, yet another DP explanation that's more along the lines of memorization compared to actual deep understanding. The existing explanation using the two-D was very intuitive.
June 8, 2020 2:18 AM
The corner case for this problem feels strange to me:
Wrong Answer
Your input: 0, []
Output: 0
Expected: 1
Can someone please explain why it expects to have 1 way to change coins
while coins.length = 0 && int amount = 0??
June 14, 2020 7:19 PM
Brute Force Recursive. TLE error
public class CoinChangeRecursiveApproach {
public int change(int amount, int[] coins) {
return change(amount, coins, 0);
}
private int change(int amount, int[] coins, int index) {
if (amount == 0) {
return 1;
} else if (index >= coins.length) {
return 0;
}
int combinations = 0;
int coin = coins[index];
int numOfCoins = 0;
while (numOfCoins * coin <= amount) {
combinations += change(amount - (numOfCoins * coin), coins, index + 1);
numOfCoins++;
}
return combinations;
}
}
Memoization Approach, accepted
public class CoinChangeMemoizationApproach {
public int change(int amount, int[] coins) {
Map<Pair, Integer> memo = new HashMap<>();
return change(amount, coins, 0, memo);
}
private int change(int amount, int[] coins, int index, Map<Pair, Integer> memo) {
if (amount == 0) {
return 1;
} else if (index >= coins.length) {
return 0;
}
Pair key = new Pair(amount, index);
if (memo.containsKey(key)) {
return memo.get(key);
}
int combinations = 0;
int coin = coins[index];
int numOfCoins = 0;
while (numOfCoins * coin <= amount) {
combinations += change(amount - (numOfCoins * coin), coins, index + 1, memo);
numOfCoins++;
}
memo.put(key, combinations);
return combinations;
}
}
xxxxxxxxxxclass Solution {public: int change(int amount, vector<int>& coins) { int n = coins.size(); int dp[n+1][amount+1]; for(int i=0;i<n+1;i++) { for(int j=0;j<amount+1;j++) { if(i == 0) dp[i][j] = 0; if(j == 0) dp[i][j] = 1; } } for(int i=1;i<n+1;i++) { for(int j=1;j<amount+1;j++) { if(coins[i-1] > j) dp[i][j] = dp[i-1][j]; else dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]; } } return dp[n][amount]; }};






